package com.darrenchan.leetcode;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-01-26 23:23
 */
public class QLint516 {
    public int minCostII(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        int K = costs[0].length;
        int[][] dp = new int[costs.length + 1][K];

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < K; j++) {
                int minValue = Integer.MAX_VALUE;
                for (int k = 0; k < K; k++) {
                    if (j != k && minValue > dp[i - 1][k] + costs[i - 1][j]) {
                        minValue = dp[i - 1][k] + costs[i - 1][j];
                    }
                }
                dp[i][j] = minValue;
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < K; i++) {
            if(min > dp[dp.length - 1][i]){
                min = dp[dp.length - 1][i];
            }
        }

        return min;
    }

    /**
     * 优化的解法
     * @param costs
     * @return
     */
    public int minCostII2(int[][] costs) {
        if (costs == null || costs.length == 0) {
            return 0;
        }
        int K = costs[0].length;
        int[][] dp = new int[costs.length + 1][K];
        //记录最小值和次小值
        int min1, min2, id1 = 0, id2 = 0;
        for (int i = 1; i < dp.length; i++) {
            min1 = min2 = Integer.MAX_VALUE;
            for (int j = 1; j < K; j++) {
                if(min1 > dp[i - 1][j]) {
                    min2 = min1;
                    id2 = id1;
                    min1 = dp[i - 1][j];
                    id1 = j;
                } else {
                    if(min2 > dp[i - 1][j]) {
                        min2 = dp[i - 1][j];
                        id2 = j;
                    }
                }
            }

            for (int j = 0; j < K; j++) {
                if (j != id1){
                    dp[i][j] = min1 + costs[i - 1][j];
                } else {
                    dp[i][j] = min2 + costs[i - 1][j];
                }
            }
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < K; i++) {
            if(min > dp[dp.length - 1][i]){
                min = dp[dp.length - 1][i];
            }
        }

        return min;
    }
}
